package com.lhcai.lc.category.prefixsum;

import java.util.HashMap;
import java.util.Map;

/**
 * 974. 和可被 K 整除的子数组
 * 可被 k 整除 ，即为K的整数倍
 *
 * @author liuhuaicai
 * @since 2024-10-19 18:22
 */
public class Lc974 {
    public static void main(String[] args) {
        Lc974 lc974 = new Lc974();
        System.out.println(lc974.subarraysDivByK(new int[]{-1, 2, 9}, 2));
    }

    public int subarraysDivByK(int[] nums, int k) {
        Map<Integer, Integer> record = new HashMap<>();
        // 初始化map 余数
        record.put(0, 1);
        int count = 0;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            // 注意 Java 取模的特殊性，当被除数为负数时取模结果为负数，需要纠正
            int modulus = (sum % k + k) % k;
            int same = record.getOrDefault(modulus, 0);
            count += same;
            record.put(modulus, same + 1);
        }
        return count;
    }
}
